package com.alexd.leetcode.contest.week101;

public class Solution3_AC2 {
	int[] pow = new int[11];

	public int atMostNGivenDigitSet(String[] D, int N) {
		int x = D.length;
		String s = N + "";
		int len = s.length() - 1;
		pow[0] = 1;
		for (int i = 1; i <= len; i++)
			pow[i] = pow[i - 1] * x;
		boolean[] bo = new boolean[10];
		for (String d : D)
			bo[d.charAt(0) - 48] = true;
		int ans = 0;
		for (int i = 1; i <= len; i++)
			ans += pow[i];
		return ans + get(bo, s);
	}

	int get(boolean[] bo, String s) {
		int ans = 0, l = s.length() - 1;
		if (l < 0)
			return 1;
		int first = s.charAt(0) - 48;
		for (int i = 1; i < first; i++)
			if (bo[i])
				ans += pow[l];
		if (bo[first])
			ans += get(bo, s.substring(1));
		return ans;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
